It has been proposed, that an address-event representation (AER) would be appropriate for communicating between plurality of senders and receivers, especially in cases where the number of senders and receivers residing on separate integrated circuit exceeds the wiring capability available between the integrated circuits (see U.S. Pat. No. 5,404,556). This approach has been originally proposed in the context of communicating neuronal activity of many artificial neurons from one chip to another. When a neuron fires a pulse (i.e., an “event”) on an event bus, the identity of a firing neuron (i.e., its “address”) could be communicated to the second chip. Since time is inherently measured across the entire system, the neuronal activity expressed in temporal periods and firing rates can be communicated to a second chip. Alternatively, time stamps could be associated with each address to preserve event timing in irregular pipelined systems.
Biological neurons fire infrequently, from a few Hz to a couple of hundred Hz. This signaling scheme saves energy in biological systems, but leaves neuronal “wiring” underutilized. It has been suggested that the speed of electronic circuits can be traded for the connectivity of nervous systems by sharing a few wires to communicate (infrequent) events from many artificial neurons while still preserving the timing of events to a very fine time scale (Mead, C. A., “Analog VLSI and Neural System”, Addison-Wesley, 1989). In fact, due to this wire resource sharing, signaling rates in artificial perceptual systems can be in order of 10 MHz (see Culurciello et al.: “Arbitrated Address-event representation digital image sensor”, Electronic Letters, Vol 37, No. 24, November 2001, pp. 1443-1445, and Landolt et al.: “Visual sensor with resolution enhancement by mechanical vibrations,” Proc. Conf. on Advanced Research in VLSI, 2001, pp 249-264).
There can be thousands of neurons firing their “events” on thousands of wires of an event bus. The task of an address-event encoder is to receive these many events, correlate the precise timing of their onset with the identity of the corresponding neuron, and timely communicate address-event pairs off-chip. It is trivial to encode an address of a single firing neuron. A problem arises when several neurons fire simultaneously thus causing event collisions at the address-event encoder and shared wiring resources.
There are two existing techniques that address the problem of address-event coding when simultaneous events occur on the event bus: arbitration and collision detection.
The first technique originally proposed by Mahowald (U.S. Pat. No. 5,404,556) and subsequently further developed by several researchers arbitrates among colliding events (see Boahen, “Point-to-point connectivity between neuromorphic chips using address events,” IEEE Tran. Circuits and Systems II, Vol. 47, No. 5, May 2000, pp. 416-434; and Deiss et al.: “A pulse-coded communications infrastructure for neuromorphic systems,” in Pulsed Nerual Networks, Maass and Bishop (eds.), The MIT Press, 1999.) It selects one event at a time, encodes that event's address, and communicates the address off chip. A binary tree search implemented in a circuit has been proposed to speed up the event selection process. Still this search takes time that is at best proportional to the number of events queued for arbitration. During that time, new events could be arriving and joining the arbitration process, causing the system to lose time associated with each event. Although a new event originates at a later point in time, as it enters the arbitration process it could be selected and read before the older event, that is still waiting a selection. One remedy for this time confusion is to latch the event bus thus keeping new events from entering the selection process until the current set of events is completely encoded. Still, some time uncertainty remains because while the current set of events is being examined, new events are queuing in the background. The time at which these new events fired is not precisely known. The best one can say is that they fired during the time period the previous set of events was handled. Furthermore, as time is spent to arbitrate events in one bus state, the chance that there will be collisions in the next bus state increases. The faster one can examine each bus state, the less chance for many collisions in the incoming event bus state. In fact, in extreme situations, the arbiter may just partially encode some events, discard the remaining events, and move on to the next sample.
Two image sensors using this kind of arbitrated address-event coding have been proposed: 1) Culurciello et al.: “Arbitrated Address-event representation digital image sensor”, Electronic Letters, Vol 37, No. 24, November 2001, pp. 1443-1445, and 2) U.S. Pat. No. 6,660,989. In the first approach pixels in an array fire at a rate that is proportional to their illumination. The arbitrated address-event encoder communicates this activity to the outside of the array. In the invention of U.S. Pat. No. 6,660,989 inventors use the method proposed by my earlier invention (U.S. Pat. No. 5,699,278) in which a single event is generated by each pixel after its reset time. U.S. Pat. No. 6,660,989 mentions that due to limited throughput of arbitrated address-event coding, the technique may be appropriate only for small imagers, recognizing the problem with arbitrated address-event encoding for large number of input events.
The second method for address-encoding—the collision detection address-event—was proposed in Mortara et al. “A communication scheme for analog VLSI perceptive systems,” IEEE Jour. Solid-State Circuits, Vol. 30, No. 6, June 1995, pp. 660-669. This method does not arbitrate but uses a binary encoder with a special collision detection code. This allows the event bus to frequently produce event addresses, but only when a single event occurs. When a single event occurs, the encoder provides a “valid” code whose value indicates the address of the event. This is communicated to the second chip. When a collision occurs on the event bus, the encoder provides an “out-of-valid-set” code indicating that the collision occurred. Generally, it is not possible to tell from this code how many and which events collided. All that can be concluded is that the collision occurred and that the system should not trust the produced code to encode any events. The encoder uses about (log 2N+2) bits to detect collision on an event bus with N wires. For example, a 1000-wire event bus would require about 10+2=12 bits. The 2 bits are necessary overhead to provide collision detection.
The collision detection address-event method has the advantage of providing event addresses within a small temporal snapshot (e.g., propagation delay of the encoder of about a few nanoseconds.) Unlike with the arbitrated approach, this technique minimizes the chance of collisions in the next time increment. However this technique is “lossy” address-event encoding since the identity of the colliding events will be unrecoverable. The argument by neorumophic engineering researchers goes that the loss due to collisions in both arbitrated and non-arbitrated cases can be tolerated in a statistical sense as the neurons periodically generate new events that are unlikely to collide in another period, therefore the receiving circuits could still be able to reconstruct neural activity received from the sender chip. However there are many important applications where address-event could be beneficial but the loss or errors cannot be tolerated.
An object of the present invention is to provide an event address encoder for lossless and substantially instantaneous production of a code that contains the identity of plural colliding events. Such a coder is useful in multi-channel analog-to-digital conversion, image sensors, and other massively parallel systems whose “cells” need to communicate their internal activity or signal levels to the outside world.